#! /usr/bin/env python

import heapq
import Image
import sys
from time import time
from PySide import QtCore,QtGui

class Cell(object):
    def __init__(self, x, y, reachable):
        """
        the cell ansich, x und y sind selbsterklaerend
        type ist walkable,impassable, some kind of walkable 
        """
        self.reachable = reachable  # fuer  den anfang ist es ein bool 
        self.x = x
        self.y = y
        self.parent = None
        self.g = 0  # wieviel kostet es mich vom start punkt aus zu dieser zelle ?
        self.h = 0  # wieviele kostet es mich von mir aus zum ziel punkt (heuristic)
        self.f = 0  # die summe aus G und H ergibt den gesammt wert der zelle
        self.diagonal = False # ob die zelle diagonal zur referenz zelle ist. das is ein versuch
        self.closed = False 

    def setReachable(self, pixel):
        walkable = (255,255,255,255) # white is walkable 
        if pixel == walkable:
            self.reachable = True
        else:
            self.reachable = False


class AStar(QtCore.QObject):
    processDone = QtCore.Signal()
    def __init__(self):
        QtCore.QObject.__init__(self)
        self.cells = []
        self.gridHeight = -1
        self.gridWidth = -1
        self.init_lists()      
        self.init_grid()
    
    def init_lists(self):
        self.op = []
        heapq.heapify(self.op)
        self.cl = set()
        self.cellsvisited = 0

    def reset_cells(self):
        for i in self.cells:
            i.parent=None
            i.g=0
            i.h=0
            i.f=0
            i.diagonal=False
            i.closed=False
       
    def init_grid(self):
        print "Initializing Grid .."
        im = Image.open(open('summonersrift-astar-map20.png',"rb"))
        self.im = im
        self.gridHeight = im.size[1]
        self.gridWidth = im.size[0]
        self.gridHeightminus = im.size[1]-1
        self.gridWidthminus = im.size[0]-1
        for y in range(0, self.gridHeight-1):
            for x in range(0, self.gridWidth-1):
                #print x,y
                tempcell = Cell(x, y, False)
                tempcell.setReachable(im.getpixel((x,y)))
                self.cells.append(tempcell)
                
        print "Grid Stats: "
        print "   Height: " + str(self.gridHeight)
        print "   Width:  " + str(self.gridWidth)
        print "   Size:   " + str(len(self.cells))
        print "Done.\n"
        self.path = QtGui.QImage(QtCore.QSize(self.gridWidth,self.gridHeight),QtGui.QImage.Format_ARGB32_Premultiplied)
        self.path.fill(QtCore.Qt.transparent)
   
    def setStart(self,x,y):
        self.start = self.get_cell(int(x),int(y))
        print self.start
        
    def setEnd(self,x,y):
        self.end = self.get_cell(int(x),int(y))
        print self.end
        
    def get_heuristic(self, cell):
        """
        rechnet den heuristischen wert aus.
        das ist wieviele x und y muss ich gehen um zum ziel zu kommen, aber wirklich laenge und breite nicht die diagonale
        """
        return 10 * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))
        
    def get_cell(self, x, y):
        """
        gibt die passende zelle zu den koordianten zurueck, da die self.cells ein eindimensionales feld ist
        wird y * width + x gerechnet
        """
        return self.cells[y * (self.gridWidth -1) + x]
          
    def get_adjacent_cells(self, cell):
        #print cell.x,cell.y
        cells = []
        #cells postions
        # -1,-1  0,-1  1,-1
        # -1,0   0,0   1,0
        # -1,1   0,1   1,1

        #x = cell.x
        #y = cell.y
        # folgendes if trifft alle zellen die innerhalb des grid liegens und eine einheit vom rand entfernt sind
        # alle die an den kanten liegen ignorier ich. weil der ist eh schwarz
        if (cell.y - 1) >= 0 and (cell.y + 1) <= (self.gridHeightminus) and (cell.x - 1) >= 0 and (cell.x + 1) <= (self.gridWidthminus):
                # -1 , -1
                tmpcell = self.get_cell(cell.x - 1, cell.y - 1)    
                tmpcell.diagonal = True
                cells.append(tmpcell)
                # 0,-1
                tmpcell = self.get_cell(cell.x - 0, cell.y - 1)    
                #tmpcell.diagonal = False
                cells.append(tmpcell)
                # 1,-1
                tmpcell = self.get_cell(cell.x + 1, cell.y - 1)    
                tmpcell.diagonal = True
                cells.append(tmpcell)
                # -1 , 0
                tmpcell = self.get_cell(cell.x - 1, cell.y)    
                #tmpcell.diagonal = False
                cells.append(tmpcell)
                # 0,0 bin ich selbst, das tumma nicht dazu
                # 1,0
                # -1 , -1
                tmpcell = self.get_cell(cell.x + 1, cell.y)    
                #tmpcell.diagonal = False
                cells.append(tmpcell)
                # -1 , 1
                tmpcell = self.get_cell(cell.x - 1, cell.y + 1)    
                tmpcell.diagonal = True
                cells.append(tmpcell)
                # 0,1
                tmpcell = self.get_cell(cell.x, cell.y + 1)
                #tmpcell.diagonal = False
                cells.append(tmpcell)
                # 1,1
                # -1 , -1
                tmpcell = self.get_cell(cell.x + 1, cell.y + 1)    
                tmpcell.diagonal = True
                cells.append(tmpcell)
        return cells

    def display_path(self,timetaken):
        print "drawing path"
        cell = self.end
        count = 0
        painter = QtGui.QPainter(self.path)
        pen = QtGui.QPen()
        pen.setColor(QtGui.QColor(255,0,255))
        painter.setPen(pen)
        thepath = []
        while cell.parent is not self.start:
            cell = cell.parent
            count += 1
            try:
                #print "path: cell: %d,%d'" % (cell.x,cell.y)
                self.im.putpixel((cell.x,cell.y),(255,0,255,255))
            except AttributeError,e:
                print e
                self.im.putpixel((self.start.x,self.start.y),(0,255,0,255))
                self.im.putpixel((self.end.x,self.end.y),(0,0,255,255))
                self.im.show()
            thepath.append((cell.x,cell.y))
            #painter.drawPoint(cell.x,cell.y)
        print "cells visited %s steps: %s - time: %s" %(self.cellsvisited,count,timetaken)
        painter.end()
        
        self.smoothpath(thepath)
        self.path.save("hurga.png")
        self.processDone.emit()
    #    self.showImage()
           
    def smoothpath(self,path):
        totallength=0
        revpath = []
        for i in reversed(path):
            revpath.append(i)
        newpath = []
        currentStart = revpath[0]
        newpath.append(currentStart)
        currentCell = revpath[1]
        for i in range(1,len(revpath)-1):
            status,deltalength = self.checkWalkable(currentStart,currentCell) 
            if status:
                currentCell = revpath[i+1]
            else:
                status,deltalength = self.checkWalkable(currentStart,revpath[i-1])
                totallength += int(deltalength)
                currentStart = currentCell
                currentCell = revpath[i+1]
                newpath.append(currentStart)
                
        newpath.append(revpath[len(revpath)-1])
        print newpath
        painter = QtGui.QPainter(self.path)
        pen = QtGui.QPen()
        pen.setColor(QtGui.QColor(255,215,0))
        painter.setPen(pen)
        for i in range(len(newpath)-1):
            x1,y1 = newpath[i]
            x2,y2 = newpath[i+1]
            painter.drawLine(x1,y1,x2,y2)
        painter.end()
        print "totallength: ",totallength
        self.calcpathlength()
        
    def calcpathlength(self):
        # this is slow and stupid but at the moment the most accurate
        count = 0 
        for i in range(self.gridWidth-1):
            for j in range(self.gridHeight -1 ):
                #print self.path.pixel(i,j)
                if self.path.pixel(i,j) != 0:
                    count += 1
        print "pixel count: ",count
        # 700 units = 70 px
        # 1px = 10 units
        # 380 u/s  default movement speed
        mvspeed = 380.0
        multiplicator = 10.0
        totalunits = count * multiplicator
        time = float(totalunits/mvspeed)
        print "time: ",time
        
    def checkWalkable(self,start,end):
        coords = self.bresenham_line(start,end)
        for i in coords:
            tempcell = self.get_cell(i[0], i[1])
            if tempcell.reachable:
                pass
            else:
                return False, None
        return True,len(coords)
        
    def bresenham_line(self,(x,y),(x2,y2)):
        """Brensenham line algorithm"""
        steep = 0
        coords = []
        dx = abs(x2 - x)
        if (x2 - x) > 0: sx = 1
        else: sx = -1
        dy = abs(y2 - y)
        if (y2 - y) > 0: sy = 1
        else: sy = -1
        if dy > dx:
            steep = 1
            x,y = y,x
            dx,dy = dy,dx
            sx,sy = sy,sx
        d = (2 * dy) - dx
        for i in range(0,dx):
            if steep: coords.append((y,x))
            else: coords.append((x,y))
            while d >= 0:
                y = y + sy
                d = d - (2 * dx)
            x = x + sx
            d = d + (2 * dy)
        coords.append((x2,y2))
        return coords
              
    def update_cell(self, adj, cell):
        """
           Update adjacent cell

        @param adj adjacent cell to current cell
        @param cell current cell being processed
        """
        if adj.diagonal:
            adj.g = cell.g + 14
        else:
            adj.g = cell.g + 10
        
        adj.h = self.get_heuristic(adj)
        adj.parent = cell
        adj.f = adj.h + adj.g

    def process(self):
        print "starting process"
        self.init_lists()
        self.reset_cells()
        self.path = QtGui.QImage(QtCore.QSize(self.gridWidth,self.gridHeight),QtGui.QImage.Format_ARGB32_Premultiplied)
        self.path.fill(QtCore.Qt.transparent)
        painter = QtGui.QPainter(self.path)
        pen = QtGui.QPen()
        pen.setColor(QtGui.QColor(22,210,230))
        painter.setPen(pen)
        starttime=time()
        # add starting cell to open heap queue
        heapq.heappush(self.op, (self.start.f, self.start))
        while len(self.op):
            self.cellsvisited += 1
            # pop cell from heap queue
            f, cell = heapq.heappop(self.op)
            # add cell to closed list so we don't process it twice
            self.cl.add(cell)
            #cell.closed = True
            #self.im.putpixel((cell.x,cell.y),(200,200,200,255))
            #painter.drawPoint(cell.x,cell.y)
            # if ending cell, display found path
            if cell is self.end:
                stoptime=time()
                painter.end()
                self.display_path(stoptime-starttime)
                break
            # get adjacent cells for cell
            adj_cells = self.get_adjacent_cells(cell)
            for c in adj_cells:
                #print c.x, c.y, c.reachable
                if c.reachable and c not in self.cl:
                    #print "meep"
                    if (c.f, c) in self.op:
                        #print c.reachable
                        # if adj cell in open list, check if current path is
                        # better than the one previously found for this adj
                        # cell.
                        if c.g > cell.g + 10:
                            self.update_cell(c, cell)
                    else:
                        self.update_cell(c, cell)
                    # add adj cell to open list
                        heapq.heappush(self.op, (c.f, c))

    def showImage(self):
        self.im.putpixel((self.start.x,self.start.y),(0,255,0,255))
        self.im.putpixel((self.end.x,self.end.y),(0,0,255,255))
        self.im.show()
        
    
                                                                
#findme = AStar()
#findme.process()
